package priorityQueue;

import java.time.LocalDate;
import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String[] args) {
        var pq = new PriorityQueue<LocalDate>();
        pq.offer(LocalDate.of(1906, 12, 9));
        pq.offer(LocalDate.of(1815, 1, 25));
        pq.offer(LocalDate.of(1903, 12, 3));
        pq.offer(LocalDate.of(1910, 6, 22));

        // 并没有排序，只是保持最小在root
        System.out.println("Iterating over elements...");
        for (var date : pq) {
            System.out.println(date);
        }

        // 并没有排序，每次移除后都把最小保持在root
        System.out.println("Removing elements...");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

// 节点i的左右子节点分别是2i+1和2i+2， 例如根节点0的左右子节点分别是1和2
// 最小堆i的值小于等于左右子节点2i+1和2i+2的值的值

// 插入时采用的shiftUp算法，先插入到数组最后，然后循环跟父节点比较，
// 如果比父节点小，则交换位置，否则停止
// 最后每个父节点都比子节点小，根节点是最小的

// 删除时采用的shiftDown算法，记录数组最后一个元素，
// 从根节点开始，找较小的子节点, 如果它不比最后一个小，则停止然后和最后一个元素交换
// 否则用较小的子节点覆盖父节点，一直这样循环，直到父节点位置大于等于总元素数量的一半,
// 因为这样的父节点已经没有了子节点
// 最后每个父节点都比子节点小，根节点是最小的

